package leecode;

/**
 * https://leetcode.cn/problems/longest-palindromic-substring/
 * 给你一个字符串 s，找到 s 中最长的回文子串。
 * <p>
 * 示例 1：
 * 输入：s = "babad"
 * 输出："bab"
 * 解释："aba" 同样是符合题意的答案。
 * <p>
 * 输入：s = "cbbd"
 * 输出："bb"
 *
 *
 * //TODO 动态规划解法待补充
 */
public class No0005_LongestPalindromicSubstring {

    public String longestPalindrome(String s) {
        String result = "";
        for (int i = 0; i < s.length(); i++) {
            String odd = odd(s, i);
            if (odd.length() > result.length()) {
                result = odd;
            }
            String even = even(s, i);
            if (even.length() > result.length()) {
                result = even;
            }
        }
        return result;
    }

    //奇数个字符串
    public String odd(String s, Integer i) {
        Integer step = 0;
        while ((i - step) >= 0 && (i + 1 + step) < s.length() && s.charAt(i - step) == s.charAt(i + 1 + step)) {
            step++;
        }
        if (step > 0) {
            return s.substring(i + 1 - step, i + 1 + step);
        } else {
            return s.substring(i, i + 1);
        }
    }

    //偶素个字符串
    public String even(String s, Integer i) {
        Integer step = 0;
        while ((i - 1 - step) >= 0 && (i + 1 + step) < s.length() && s.charAt(i - 1 - step) == s.charAt(i + 1 + step)) {
            step++;
        }
        if (step > 0) {
            return s.substring(i - step, i + 1 + step);
        } else {
            return s.substring(i, i + 1);
        }
    }

    public static void main(String[] args) {
        No0005_LongestPalindromicSubstring a = new No0005_LongestPalindromicSubstring();
        System.out.println(a.longestPalindrome("ababc"));
    }

}
